package com.LC._78;

// DFS和回溯法主要区别在于状态重置，DFS在访问过一个结点之后会标记为访问过，这个标记不会被撤销。回溯法也会对结点进行标记，但是在回溯之后会撤销这个标记。例如寻找条路径，DFS在找到一条后就会结束，回溯法可以将所有的路径找到。
//从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到” 尽头 “的时候, 再倒回出发点, 从另一个可能出发, 继续搜索. 这种不断” 回溯 “寻找解的方法
// class Solution {
//     public List<List<Integer>> subsets(int[] nums) {
//         List<List<Integer>> res = new ArrayList<>();
//         backtrack(0, nums, res, new ArrayList<Integer>());
//         return res;//三步走
//     }
//     //
//     private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> tmp) {
//   res.add(new ArrayList(path))：开辟一个独立地址，地址中存放的内容为path链表，后续path的变化不会影响到res

//   res.add(path)：将res尾部指向了path地址，后续path内容的变化会导致res的变化。
//注 引用里存的引用也会随着实例对象的改变而改变。
//         res.add(new ArrayList<>(tmp));//从空数组开始加
//         for (int j = i; j < nums.length; j++) {//结束的条件只要这一层没有进入递归就算结束
//             tmp.add(nums[j]);//j = 递归返回的j+1;
//             backtrack(j + 1, nums, res, tmp);//
//             tmp.remove(tmp.size() - 1);//一定要在递归函数的下面->返回上一级->前一个数字
//         }
//     }
// }
// result = []   //结果集
// def backtrack(路径, 选择列表):
//     if 满足结束条件:
//         result.add(路径)  //把已经做出的选择添加到结果集；
//         return  //一般的回溯函数返回值都是空；

import java.util.ArrayList;
import java.util.List;

//     for 选择 in 选择列表: //其实每个题的不同很大程度上体现在选择列表上，要注意这个列表的更新，
//     //比如可能是搜索起点和终点，比如可能是已经达到某个条件，比如可能已经选过了不能再选；
//         做选择  //把新的选择添加到路径里；路径.add(选择)
//         backtrack(路径, 选择列表) //递归；
//         撤销选择  //回溯的过程；路径.remove(选择)
//class Solution {
//    public List<List<Integer>> subsets(int[] nums) {
//        List<List<Integer>> res = new ArrayList<>();
//        backtrack(0, nums, res, new ArrayList<Integer>());
//        return res;//三步走
//    }
//    //
//    private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> tmp) {
//// res.add(new ArrayList(path))：开辟一个独立地址，地址中存放的内容为path链表，后续path的变化不会影响到res
//
//// res.add(path)：将res尾部指向了path地址，后续path内容的变化会导致res的变化。
////注 引用里存的引用也会随着实例对象的改变而改变。
//        res.add(new ArrayList<>(tmp));//累计保存
//        for(int j=i;j<nums.length; j++){
//            tmp.add(nums[j]);//x
//            backtrack(j+1 , nums , res , tmp);
//            tmp.remove(tmp.size()-1);//删除最后一个元素
//        }
//    }
//
//}

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack( 0,nums, res  ,new ArrayList<>());
        return res;//三步走
    }

    private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> temp) {
//        if()
        res.add(new ArrayList<>(temp));//开辟一个独立地址，地址中存放的内容为path链表，后续path的变化不会影响到res
        for(int j=i;j<nums.length;j++){
            //! 回溯写在循环体内
            temp.add(nums[j]);
            backtrack(j+1 , nums , res , temp);
            temp.remove(temp.size()-1);
        }
    }
}